1. Field of the Invention
The present invention relates to a discrete pattern. More particularly, the present invention relates to a discrete pattern having low discrepancy and including a pattern of dots arranged so there is no overlapping, an optical member, a light guide plate, a side light device and a light-transmitting liquid crystal display device that uses the discrete pattern, and to a method and a program for generating the discrete pattern, a computer-readable storage medium on which a computer-readable program is stored for generating the discrete pattern, and a discrete pattern generation system.
2. Background Art
Various techniques using discrete pattern are known. These techniques are used for a light guide plate, for example, of light-transmitting liquid crystal display device or a diffuser sheet, and the discrete pattern can be, for example, a dithering pattern, a lithography photomask pattern or a pattern for stopper. Recently, the application of a discrete pattern for a DNA arrangement on a DNA chip has also been discussed.
Conventionally, a discrete pattern is formed so that dots are arranged at random by using a so-called random-number generator, or the dots are arranged on a regular orthogonal lattice, such as plotting paper. However, with the conventional methods, the following problems have arisen for the random pattern that is generated merely by a common random-number generator. Specifically, even when dots are arranged at random, the overlapping of dots and uneven dot densities, which occur because each dot has a definite size, can adversely affect the appearance of a dot pattern, and an optical malfunction, such as uneven luminance, can occur. Further, when the dots are regularly arranged, an undesirable optical pattern, such as moire, can occur due to an interference between dots or with an external regular pattern.
To resolve the problem, a method is proposed in Japanese Unexamined Patent Publication No. Hei 10-153779 whereby an irregular pattern is generated without an excessive approach between the dots. According to this method, first, as an “absolute random number arrangement method”, (1) the initial position (x, y) is provided for all the dots by a random-number generator; and (2) a random number is again generated for the overlapping dots and their positions are corrected. However, as for the calculation method disclosed in Japanese Unexamined Patent Publication No. Hei 10-153779, it is well known that the calculation performed to eliminate the overlapping of dots can not be convergent in an area having a dot filling rate of more than 50%. Specifically, when the method described in Japanese Unexamined Patent Publication No. Hei 10-153779 is used, it is quite difficult for an irregular pattern having no abnormal approach between dots to be generated, while maintaining randomness. Further, according to this method, which is based on the generation of multiple pseudo random numbers, it is also difficult to remove an uneven portion from a dot pattern, even if overlapping of dots can be removed from an area having a low dot filling rate.
FIG. 1 is a diagram showing an example dot pattern that is formed by the method described in Japanese Unexamined Patent Publication No. Hei 10-153779. The dot pattern in FIG. 1 is generated using a process whereby (1) dots are arranged at two-dimensional regular lattice points formed by linear lines or curves, and these positions are defined as initial positions; (2) the displacement of each initial position is provided by a random-number generator; and (3) a random number is again generated for the overlapping dots and their positions are corrected. As is shown in FIG. 1, according to this method, the dots can be arranged without overlapping, so long as only small displacements of the lattice points are maintained. However, according to a method for generating a random position as a perturbation from a lattice point, in an area having a comparatively high dot filling rate, such as a ratio exceeding 50%, it is difficult to generate a satisfactory irregular pattern while avoiding the occurrence of moire. Further, according to this method, which is based on the multiplex generation of pseudo random numbers, many aggregations of dots appear even if dot overlapping is removed, and it is difficult to generate a uniform random pattern.
The reasons for this will be explained. For the conventional example using random dots, assume that the size of the dots being arranged is about 100 μm and that the filling rate is 70%. As is shown in FIG. 1, the shape of a dot is assumed to be a square. With this dot size and the filling rate described above, an interval of merely 20 μm is generated between the dots. In FIG. 1, dots 100 and intervals 102 between the dots 100 are shown at an exact reduced scale. When random perturbation is provided for the regular lattice, dots 104, indicated by broken lines in FIG. 1, are obtained. It is understood that these dots 104 can only generate a pattern having an extremely limited irregularity (hereinafter referred to as randomness in this invention), as is shown in FIG. 1. Because the adjacent dots do not jump over each other, and because the filling rate is high, the positions of these dots are corrected only within a limited range.
A square lattice is employed in the conventional art in FIG. 1. However, under a condition wherein dots should not be arranged too closely together, the randomness of the dot pattern is more or less limited, even for other types of regular lattices. That is, according to the method whereby a predetermined dot is provided at an initial position and perturbation is employed to generate a random arrangement, in principle, as the filling rate increases, the possibility that a random dot pattern will be obtained that closely resembles a truly random arrangement decreases. Therefore, regardless of the filling rate, this method is not satisfactory for the generation of random patterns.
In addition, relative to the optical characteristic of a dot pattern generated by the above method, another problem has arisen in that a moire pattern will occur when a light beam is transmitted through or reflected from a dot pattern. Conventionally, in the printing field, many studies and proposals have been made to devise methods for removing moire. For example, in Japanese Unexamined Patent Publication No. 2000-94756, for a halftone process performed by a printer, a printing technique is disclosed for avoiding the occurrence of moire (so-called uneven feeding and uneven lines) caused by regular printing fluctuations, produced by the rotation of a paper feed drum, and printing dot patterns.
Therefore, in Japanese Unexamined Patent Publication No. 2000-94756, printing dots are arranged at random. That is, perturbation is provided at random for printing dots arranged on a regular lattice, an improvement that satisfactorily precludes the occurrence of the uneven dot densities that accompany the appearance of moire. However, for the above mentioned reasons, it is difficult for the randomness of this method to be directly applied for uniform discrete patterns.
The above problems, including the generation of random dot patterns and the occurrence and removal of moire, arise not only in the printing field, wherein printing techniques for printers are affected, but also in various other fields, such as the production of display devices that include rear lighting devices (hereinafter referred to as backlights).
As a specific example, since light, compact light-transmitting liquid crystal display devices can be made that consume little power, the production and use of these display devices have become ever more important as a core technique affecting the selection of hardware for use in the so-called IT revolution. However, since unlike conventional display devices, i.e., CRTs, liquid crystal devices do not emit light, backlight units must be provided that light all the liquid crystal cells in these devices. This is especially true today, since there is an increased demand for liquid crystal display devices having high resolution color displays, so that accordingly, a fervently desired characteristic of backlight units is that they uniformly, and brightly, illuminate large areas.
FIG. 2 is a diagram showing a light-transmitting liquid crystal display device, a typical display device that includes a backlight unit. An explanation will now be given, using the light-transmitting liquid crystal display device in FIG. 2, for a countermeasure for random dot patterns and moire. As is shown in FIG. 2, a conventional light-transmitting liquid crystal display device includes a backlight unit. The backlight unit includes: a light guide plate 108, on which a random dot pattern 106 is formed; a fluorescent tube CFL, which is arranged adjacent to the light guide plate 108; a reflector 112, which covers the fluorescent tube CFL to ensure efficient transmission, to the light guide plate 108, of light emitted by the fluorescent tube CFL; and a reflection sheet 114, which is used to efficiently reflect, to a liquid crystal panel (not shown), light scattered by the light guide plate 108.
Since, to the extent possible, the dot pattern 106 on the light guide plate 108 is formed at random, problems such as those presented by moire are resolved. As is shown in FIG. 2, a diffusion sheet 116 and prism sheets 118a and 118b, provided for the backlight unit, regulate the distribution of the light irradiating the liquid crystal panel.
The side light type backlight unit shown in FIG. 2 is frequently employed for small devices, such as notebook computers. In the backlight unit in FIG. 2, light emitted by a cold cathode fluorescence light (CFL), such as a fluorescent tube, is scattered by the dot pattern 106 formed on the bottom of the light guide plate 108, which is made of an acrylic resin, or the reflection sheet 114, which is arranged below the light guide plate 108. The thus scattered light is then transmitted to the liquid crystal panel (not shown), passing en route through the diffusion sheet 116 and the prism sheets 118a and 118b, which are arranged above the top face of the light guide plate 108. The thus distributed light can then be viewed by a user. That is, the backlight unit shown in FIG. 2 is a device for converting a line light source into a flat light source.
So long as the so-called side light device shown in FIG. 2 is employed, a mechanism for scattering light emitted by a light source and for reflecting the scattered light onto a liquid crystal panel is indispensable, and is an important device mechanism for improving the luminance produced by the backlight unit. Therefore, various studies have been initiated to examine manufacturing processes employed for the bottom of the light guide plate 108 or for the reflection sheet 114. For example, in Japanese Unexamined Patent Publication No. Hei 8-085001, the bottom of a light guide plate is processed by a cutting tool having a negative rake angle, so that the resultant irregular surface works as the light scattering plane. However, according to this method, it is difficult to quantitatively control the uniformity of the luminance provided by a backlight unit, and since scattered light is wasted due to its deflection in light scattering directions, the method is not appropriate for obtaining a high quality backlight unit that provides a high luminance.
Other methods have also been proposed: a method in Japanese Unexamined Patent Publication No. Hei 7-294745, whereby a groove having a recessed portion in cross section is formed in the bottom of a light guide plate and for scattering light on the top face of the light guide plate; and a method in Japanese Unexamined Patent Publication No. Hei 6-242320, whereby a pattern coated with a particle pigment, such as titanium dioxide, is formed on the bottom of a light guide plate. The above conventional methods include the same feature that provides for the formation of a light scattering structure having a specific geometrical, cyclic design, i.e., a dot pattern, is formed on a light guide plate. However, since generally an element including a small cyclic pattern, such as a color filter or a prism sheet, is indispensable for a liquid crystal display device, when the arrangement of a dot structure is cyclic, the dot structure and the light optically interfere with each other and generate a moire pattern. Since this moire pattern drastically deteriorates the value of a luminous object as a light source, it is preferable that, to the extent possible, the occurrence of moire be avoided.
Relative to the moire pattern described above that occurs as a result of a dot pattern formed on the light guide plate 108 of a display device, such as a light-transmitting liquid crystal display device using a backlight unit, the reduction of moire, as it is related to the various device techniques described above, has also been discussed.
For example, in Japanese Unexamined Patent Publication No. Hei 9-269489, a method for scattering light is disclosed whereby multiple, small light-scattering members, such as micro dots, are arranged at random on the bottom of a light guide plate. Further, an improved method is disclosed in Japanese Unexamined Patent Publication No. 2000-171797, and a method is disclosed in Japanese Unexamined Patent Publication No. Hei 11-250713 whereby dots are arranged at random on the top of a light guide plate in order to employ them for a reflection type liquid crystal display device. FIG. 3 is a diagram showing a conventional example for which a dot pattern generated at random is employed for a reflection type liquid crystal display device.
In the conventional case in FIG. 3, a light guide plate on which a random dot pattern is formed using a pseudo random number is used to constitute a backlight unit. In the backlight unit in FIG. 3, a fluorescent tube CFL and a reflector 124 are arranged adjacent to a light guide plate 122 on which multiple dots 120 are formed at random using a pseudo random number. The light guide plate 120, the fluorescent tube CFL and the reflector 124 in FIG. 3 are supported by a frame 126 and together constitute a backlight unit that reflects light in the direction indicated by an arrow A. As is explained while referring to FIG. 2, but not shown in FIG. 3, a reflection sheet, a diffusion sheet and a prism sheet are arranged on the backlight unit in FIG. 3.
Because of an optical need for the intensity of scattered light to be uniform across the entire light guide plate 122 that is used for the conventional backlight unit in FIG. 3, it may be necessary for the dot filling rate distribution, for example, to be continuously changed in the center area and in the four corner areas of the light guide plate 122. Therefore, a simple method has been studied that calls for the provision of an initial position to satisfy the obtained continuous distribution of the filling rate. For example, a method has been studied for forming a pattern wherein the filling rate is continuously changed by coupling areas having different lattice intervals. However, with this method, a defect encountered in many cases is that at the boundaries where filling rates are changed the seams are visible.
These seams can also be reduced by generating, across the entire plane on which dots are formed, a two-dimensional lattice whose shape is continuously changed to match the obtained filling rate distribution. However, excluding a case wherein the distribution is provided by a simple and easy analysis function, high level and extensive calculations are required for the generation of a lattice. That is, the conventional method used for calculating perturbations based on a lattice point is inadequate, not only for irregularities, but also for coping with the filling rate distribution.
For the above backlight unit, there is also a proposal according to which the structure is changed in order to improve the luminance or the angle of incidence of light. For example, a backlight unit wherein prisms are formed directly on the top of a light guide plate is proposed in “'99 latest liquid crystal process technique”, Yoji Oki and Minoru Katsumata, Press Journal, Sep. 10th, 2000, page 441. In addition, it is also proposed that an optical sheet, such as a diffusion sheet or a prism sheet, is not provided.
However, since the above proposals require that precise control be provided for the scattering mechanism of the light guide plate, the probability of occurrence of moire or an interference stripe will be increased, and stricter discussion of a method to be used for the reduction of moire is required. Furthermore, a discrete pattern, including a dot pattern having a higher quality, must be provided because the abovementioned conventional pseudo random dot patterns are inappropriate for coping with a high filling rate distribution, the uniformity of dot patterns is inappropriate, and depending on the structure of a backlight unit, the occurrence of a specific type of interference stripe can not be avoided. To provide this discrete pattern, a method is required whereby, in addition to the randomness of the discrete pattern, an index for a uniformity must be introduced to generate a random discrete pattern that satisfies a stricter condition.
Recently, to solve a problem wherein sample points are irregularly and uniformly extracted from a predetermined area in multi-dimensional space, the use of the LDS method has been discussed, especially for a mathematical field, such as numerical integration. For example, in “IPSJ Magazine”, Yoichi Ninomiya et al., Vol. 39, 1998, page 794, teaches that by using samples that are distributed irregularly and uniformly in an overall multi-dimensional space by using a determinative LDS, such as the Faure sequence or a Sobol sequence instead of pseudo random number, the price of a derivative can be quickly and accurately calculated by approximating a multi-dimensional integration solution as is done using the Monte Carlo method.
Further, as is explained in U.S. Pat. No. 5,872,725 and in Japanese Unexamined Patent Publication No. Hei 11-259452, the upper bound of discrepancy, which is a measure of a non-uniformity of point sets, is limited by an inequality in the above sequences. By using these sequences, the convergence of a multi-dimensional integration calculation, such as is used for the Monte Carlo method, can be quickly performed. Further, the use of numerical integration employing the LDS method is reported in order to increase the rendering speed attained by the ray tracing method.
As is described above, a pseudo random dot pattern that depends directly on randomness is inappropriate for an optical member that provides a preferable light guide plate, a backlight unit that uses the light guide plate, and a light-transmitting liquid crystal display device that uses this backlight unit. Therefore, a new method is required for controlling discrepancy and for generating an initial distribution. In this invention, a “discrepancy” is an index for the uniformity of the distribution of dispersed dots, as is described in “Discrepancy for points”, for example, by Tezuka, in “Discrete structure and algorithm IV”, edited by Kazuo Murota, Modern Science, Chapter 3.
Further, in halftoning which is a technique employed by printing or photocopying to express an image comprising a continuous tone such as a silver salt photograph film, that is to say, a continuous-tone image with a medium capable of only a binary expression, a discrete dot pattern also need be treated. In the fields of printing and photoengraving, the halftoning is also called “halftone printing”. More generally, it can be said that said technique is a halftoning method to express a gradation of an image by densities of minute dots.
In recent years, since an industrial need for such halftoning method has become extremely large along with progress of printer and facsimile technologies, a variety of techniques have hitherto been proposed. The method to express a gradation by densities of minute dots having equal sizes is hereinafter called “FM (frequency modulated) screen method” although said method is expressed differently in different types of literacy. Said FM screen method is roughly classified into an error diffusion method and a mask method from a viewpoint of calculation method.
The error diffusion method tries to retain an image density by converting an input image into a binary image or a multiple-valued image by comparing said input image to a threshold value and then diffusing an error generated between an output value and input value at said conversion by weighting thereof to a predetermined nearby pixel group. In this case, pixels of the input image and the output image correspond to each other at the ratio of 1 to 1. An image output by said method is put into a practical use in a wide range since said image is assumed to have a relatively fine image quality and an excellent resolution. Said method however requires a somewhat complicated calculation for each pixel in comparison to the mask method which simply carries out the halftoning by comparing an input image to a given threshold value. Further, since dot strike positions differ depending on an input image, there is a difficulty in predicting a degree of a color mixture resulting in poor reproduction of colors. Further, the fact that a transient region appears in a boundary region whereto the error diffusion method is applied and the fact that a false image called “worm” or “serpentine raster” is often observed are assumed to be unresolved problems (P. 295 of Takashi Yahagi, “Multimedia and Digital Signal Processing” by Coronasha, 1997). In addition, electronic hardware has been progressed remarkably in recent years and so an amount of calculation that increases along with the error diffusion is not a fatal problem. Problems related to an image quality however are assumed to require improvement.
In order to reduce problems of the error diffusion method related to an image quality, many trials such as changing a distribution of error allocation to peripheral regions (there are a variety of distributions, e.g., the Floyd-Steinberg method and the like) and optimizing a scanning direction of the diffusion (refer to, e.g., T. Asano, “Digital halftoning algorithm based on random space-filling curve”, Proc. International Conference on Image Processing, 1996, 545). In the method of distributing an error of one pixel to peripheral limited regions, a certain degree of problem arising related to an image quality is essentially inevitable. The reason why is that distinction of an error occurrence side and a side taking charge of an error is adopted to the error diffusion method depending on a scan direction and such distinction is merely artificial as long as dots constituting a binarized image are equal.
The same can be said regarding halftoning of an image. Essentially, the binarized image must be determined so that an entire original image is reproduced correctly. A method of adopting a relationship between pixels in consideration of either the binarized image or the original image is essentially a mere approximation. As apparent from the foregoing description, improvement of the error diffusion method has a long history. Any improvement made in said history however is like a symptomatic treatment on premise of existence of an error diffusion algorithm. The best halftoning algorithm is perhaps an algorithm based on mutual relationships between all pairs of dots. An algorithm also capable of reproducing a gradation gradient however has not been known.
Ulichney's standards related to a quality of a binarized image and the conventional technique of the mask method are further described hereinafter. Ulichney presents the two conditions given hereunder as visually preferable conditions for an FM screen pattern (R. A. Ulichney, Proceedings of the IEEE, 76 (1988) 56):
1. a radius Fourier component related to a dot distribution has a “blue noise” characteristic, and
2. a dot distribution is isotropic.
Said references are currently accepted in a wide range as standard indexes for evaluating an image quality.
The discovery by Ulichney has been proposed along with a directionality of improving the error diffusion algorithm. Thereafter, application of said knowledge to the mask method to construct the halftoning method partly supplementing a defect of the error diffusion method has been studied. That is to say, a way of producing a mask that gives a threshold value at halftoning so that said quantitative references presented by Ulichney are satisfied was worked out. This method is often called “blue noise mask method”. Representative thesis thereof is Mitsa-Parker (T. Mitsa and K. J. Parker, J. Opt. Soc. Am. A, 9 (1992) 1920). Similarly, Japanese Patent No. 2622429 and U.S. Pat. No. 5,111,310 may be enumerated as theses that generally describe the conventional methods.
FIG. 4 is a schematic view showing processing of the mask method (systematic dither method). FIG. 4(a) shows a read image, FIG. 4(b) shows a dither matrix, and FIG. 4(c) shows a displayed image. In general, the mask method carries out the halftoning by comparing a read image to a given threshold value of a matrix. FIG. 4 shows the simplest mask method wherein original pixels of an original image and a binarized image correspond to each other at a ratio of 1 to 1. In FIG. 4, the method to determine black and white of a binarized image from a magnitude relationship between a value shown in a mathematical table called “dither matrix” and a brightness value of an original image after comparing thereof. The objective of the blue noise mask method is to make a resulting binarized image (shown in FIG. 4(c)) have an isotropic blue noise characteristic. Accordingly, it can be said that the halftoning issue of a continuous-tone image is essentially equal to the optimization issue of a dot pattern. The blue dot characteristic denotes a discrete pattern wherein dot distribution is centered at a principal wavelength related to a ratio between an area of each dot and a filling factor in a predetermined gradation level ideally.
The mask method further includes a method of corresponding a dot pattern comprising a large number of dots to one original pixel. Said method is called “one-to-multiple mask method” and the method shown in FIG. 4 is called “one-to-one mask method” for convenience.
As apparent from the foregoing description and as described in details in Japanese Patent Laid-Open No. 2000-59626, most current halftoning methods are designed based on said Ulichney's standards. As presented by Ulichney based on the error diffusion method, it has been known that a binarized image satisfying the Ulichney's standards actually becomes a smooth image having neither a roughness nor a geometrical pattern. The Ulichney's standards however have a defect of restrictions on a quantity of macros and said standards are therefore inappropriate as direct standards for real production of macros. More specifically, even if conditions for a preferable power spectrum (equal to Fourier transformation of an autocorrelation function related to dot position distribution according to the Wiener-Khinchin's theorem) are presented, it is not easy to create a dot pattern or a threshold value mask based on the dot pattern. Further, even if a restriction on an isotropy is given, the method to realize thereof is not self-evident. Such problems are also applicable to series of studies related to the “green noise mask” method by Lau, et al. (refer to, e.g., D. L. Lau, G. R. Arce, and N. C. Gallaghe, Proc. IEEE, 86 (1998) 2424).
Further, the Ulichney's conditions are unsatisfactory in that there is no effective index directly denoting an unevenness of a dot pattern. In fact, a dot pattern based on a white noise (specifically, a pattern wherein dot positions are sampled randomly with pseudo-random numbers) is given according to Ulichney (R. A. Ulichney, Proceedings of the IEEE, 76 (1988) 56). Said dot pattern however is judged to be “completely isotropic (−10 dB)” at a quantity corresponding to the Ulichney's anisotropy.
The present situation of the one-to-multiple blue mask method is further described hereinafter. U.S. Pat. No. 4,920,501 discloses a halftoning method to provide dot patterns having blue noise characteristics for individual brightness values and replace original pixels by said dot patterns according to the brightness values of the original pixels. Primarily, an overview of the one-to-multiple mask method is shown in figures. As shown in FIG. 5, an original image OP is divided into small blocks (FIG. 5(a)). Select a dot pattern of a spread-out type dot pattern corresponding to a representative brightness value (defined to J) of the original image OP divided into small blocks (FIG. 5(a)). Said spread-out type dot pattern becomes a binarized image of a small block (FIG. 5(c)). In FIG. 5, the number of gradations is specified to 256 gradations and 256 dot patterns thereof are assumed to be stored in a memory in advance. The method disclosed in U.S. Pat. No. 4,920,501 is listed below.
1. Determine a size of a mask and then determine the number of dots appropriate for a gradation.
2. Distribute dots randomly on a mask with pseudo-random numbers.
3. Calculate a visual cost function.
4. Select one pixel randomly from black (1) pixels of a mask, one from white (0) pixels and then exchange values thereof.
5. Calculate a visual cost function based on a new disposition and obtain a difference from a previous visual cost function Δc.
6. Obtain a Boltzmann statistic as against Δc and a “temperature” T, compare the Δc value and a random number value and determine whether or not to adopt a new disposition. When the new disposition is determined not adopted, return to 4.
Characteristics of the dot pattern generation method are that initial disposition is generated with random numbers and said initial disposition is relaxed by a simulated annealing method (refer to Section 9.4 of Hidenori Nishimori, “Spin glass theory and information statistical dynamics”, published by Iwanami Shoten, 1999). Said conventional method presents that frequency characteristics of the initial disposition having a white noise characteristic may be improved by employing an optimization method. Said conventional method further presents that said algorithm may produce a blue mask fairly satisfying the Ulichney conditions. The initial disposition generated with pseudo-random numbers however has a defect of an apparently great unevenness and so it is impossible to binarize the initial disposition as is in high quality.
Improvement of said method is studied in Japanese Patent Laid-Open Publication Heisei No. 10-275228. According to a method disclosed in Japanese Patent Laid-Open Publication Heisei No. 10-275228, the simulated annealing method is employed to determine other patterns sequentially from a halftone pattern as an initial pattern so that Mitsa-Parker conditions described later. Said initial patterns are not determined with random numbers like “darts”, but adoption of an appropriate pattern by the conventional technique is merely instructed. In either way, patterns are created in procedures of initial position generation and optimization in this order disclosed in Japanese Patent Laid-Open Publication Heisei No. 10-275228.
As disclosed in Japanese Patent Laid-Open Publication Heisei No. 10-275228 however, if halftone patterns are selected appropriately based on the Ulichney's standards, a multi-gradation pattern generated from said halftone patterns are always somewhat not being unoptimized inappropriately. For example, dot patterns are assumed to be optimized so that spaces between most adjacent dots are mostly concentrated to a specific value. Then, when one dot is added to said dot pattern, a field having unoptimized spaces between dots always appears in the vicinity of said dot. The reason why is because already-created dots are assumed to be fixed.
Specifically, said methods have principle defects from the viewpoint of optimizing a dot pattern. Further, no specific improvement of an optimization method for a start pattern is studied in Japanese Patent Laid-Open Publication Heisei No. 10-275228.
Furthermore, optimum halftoning by the one-to-one blue mask method is not yet satisfactory and so a variety of types of improvements are being studied. Mitsa and Parker explain that the conditions represented by the formula given hereunder must be satisfied when producing a one-to-one blue mask (T. Mitsa and K. J. Parker, J. Opt. Soc. Am. A, 9 (1992) 1920):if g2>g1∩p(i, j; g1)=1p(i, j; g2)=1(wherein p(i, j, g2) denotes an output value (0 or 1) of an (i, j) block in a mask pattern of a g2 gradation. Said condition describes that “when the (i, j) block in a g1 gradation is black, the same block in the g2 gradation higher than the g1 gradation is also black”. Said condition is hereinafter called “Mitsa-Parker condition” for convenience. As described in details in Japanese Patent Laid-Open Publication No. 2000-59626, when said Mitsa-Parker condition is satisfied, a threshold value mask (wherein 256 gradations are assumed) may be created from the relationship represented by the formula given hereunder.       m    ⁢                   ⁢          (              i        ,        j            )        =      256    -                  ∑                  g          =          1                256            ⁢              p        ⁢                                   ⁢                  (                      i            ,                          j              ;              g                                )                    
Specifically, the threshold value mask for the one-to-one mask method may be employed to produce a threshold value mask for a one-to-one mask under the Mitsa-Parker condition.
On premise of said fact, a production method of a threshold value mask having a blue noise characteristic is disclosed in Japanese Patent Laid-Open Publication No. 2001-298617. According to said method, high-gradation patterns are produced sequentially in procedures of giving repulsion potentials to dots in a gradation pattern of a previous stage (lower) and creating new dots on the lowest point of the potentials in this order starting from a low-gradation dot pattern (wherein a regular dither method based on a Bayer matrix is employed to create dots). Disclosed in Japanese Patent Laid-Open Publication No. 2001-298617 is that said principle may be employed to produce a homogeneous dot pattern having a blue noise characteristic. In addition, said publication's example is essentially equal to the method described in W. Purgathofer, R. F. Tobler, and M. Greler, Proceedings of the International Conference on Image Processing, 1032 (1994). The article also proposes the repulsion potential represented by the formula given hereunder:             V      ⁡              (        r        )              =          exp      ⁡              (                  -                                    (                              r                s                            )                        p                          )              ,wherein r denotes a distance from a dot. The formula described above indicates that the potential decreases rapidly when the distance exceeds a values. Said method may be interpreted to a trial of changing an expression of the Ulichney standards to a micro expression. The reason why is that Ulichney states that a pattern having a blue noise characteristic may be created when spaces between most adjacent dots are concentrated properly around a “principal wavelength”. A technique to obtain a preferable spectrum characteristic of a pattern from such a viewpoint has not yet been proposed.
The method proposed by W. Purgathofer, R. F. Tobler and M. Greler and the method disclosed in Japanese Patent Laid-Open Publication No.2001-298617 are not satisfactory as dynamic mitigation processes. Dot patterns are assumed to be optimized so that the spaces between most adjacent dots are mostly concentrated to the value s in the specific gradation as described above. Then, when one dot is added to said dot pattern, a field having unoptimized spaces between dots always appears in the vicinity of said dot. The reason why is because already-created dots are assumed to be fixed.
More recently, Hiller, et al. have proposed a strong mitigation algorithm (S. Hiller, O. Deussen, and A. Keller, “Tiled Blue Noise Samples”, Proceedings of the 6th International Fall Workshop on Vision, Modeling, and Visualization 2001, in press). It is reported that the method proposed by Hiller, et al. is employed to generate a dot pattern with pseudo-random numbers and then a mitigation algorithm called “Lloyd method” is applied to generate a dot pattern having a blue noise characteristic in high-speed. The Lloyd's method is to level spaces between most adjacent dots by repeating an operation of moving dots to a gravity center of each Voronoi polygon based on so called Voronoi division. FIG. 6 shows said method. FIG. 6(a) shows randomly generated initial positions and Voronoi division thereof, FIG. 6(b) shows a process of Lloyd mitigation and FIG. 6(c) shows a dot pattern after the mitigation. Hiller, et al. further emphasizes that an even binarized image may be generated without a problem, e.g., a joint between blocks or the like, by also generating Voronoi diagrams on boundaries appropriately.
Said method improves problems peculiar to the mitigation process so-far described. Specifically, even patterns are generated by mitigating all dots without dividing dots into relaxed dots and mitigating dots. Moreover, the principle of mitigation is based on a method of directly optimizing spaces between most adjacent dots.
However, it is clear that the method of Hiller, et al. has two defects. The first defect is that it is difficult to create a dot pattern having a gradually changed gradation by said method based on the Voronoi division. The second defect is that use of pseudo-random numbers for generation of initial positions results in unevenness in a relaxed pattern.
As is apparent from the foregoing description, a method of enabling generation of a pattern having sequential filling factor distributions to an area of a high filling factor exceeding 50% without an optical defect that can be observed visually is not available. Further, imposing a strong upper limit to filling factors is a great hindrance in controlling a brightness, a transitivity and a reflection factor. Therefore, it has been desired that a filling factor distribution to be given satisfactory without causing moiré while giving a higher flexibility by generating a discrete pattern without being restricted by mutual influences of filling factors even when a filling factor distribution exists. Moreover, the method of employing the pseudo-random number generation method to generate a random dot pattern may not deal with a high filling factor and, in addition, said method has defects regarding computer resources of a large deviation in a dot distribution and a time of work required for correction thereof.
Specially, when an arbitrary filling factor distribution from a low filling factor to a high filling factor is given, proposal of an ideal generation method for a dot pattern has been required for existence of a sharp filling factor gradient wherein a change in a filling factor per dot diameter exceeds 1%. Further, manufacturing of optical components that do not cause errors, e.g., unevenness, coloring, moiré and the like, by employing said method to generate dots on a shading film, a photomask and the like. A dot pattern generating method that may retain a filling factor distribution appropriately by adding or deleting dots suitably when a filling factor gradient is specially sharp has also been required.
Further, the contents equivalent to the Ulichney standards described with macro languages may be described by employing only micro quantities that define dot positions and so an algorithm to specifically realize said description is required. Still further, if a generation method for a dot pattern that proposes a quantitative standard regarding unevenness insufficiently expressed by the Ulichney standards and then specifically satisfies said quantitative standard, said generation method for a dot pattern yields a considerable profit in practical use.
Still further, sizes after tile-like division are almost determined by a resolution of an output side and numbers of bits required to express a gradation and said sizes impose a restriction on a method of removing sensible artifacts. It is possible to remove said restriction by permitting gradation gradients in tiles wherein the halftoning method has been required.
Still further, proposal of an algorithm representing the Ulichney standards in a form of being directly related to micro quantities that define dot positions has been required.
Furthermore, proposal of an algorithm representing the Ulichney standards in a format of direct connection to a micro quantity for defining dot positions is desired.
That is to say, a generating method for discrete patterns disposed sufficiently randomly having low discrepancies and which do not overlap with each other has been required.
Further, a generation method for a discrete pattern enabling the above-described dot patterns to be disposed sufficiently randomly regardless of filling factors has been required.
Still further, a program for generating said discrete patterns and a storage medium wherein said program is stored have been required.
Furthermore, optical components comprising said patterns have been required.
Further, an optical waveguide comprising said discrete patterns and a back light unit comprising said optical waveguide have been required.
Still further, a transmissive liquid crystal display device comprising said back light unit comprising said discrete patterns has been required.
Still further, a discrete pattern generation system for generating said discrete patterns has been required.